package LimitedTimeGame.Day_0304;

/**
 * @author zxc
 * @date 2023/03/04 09:23
 **/

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;

/**
 * 题目 ：排序数组
 * 题目详述 ：
 * 给你一个整数数组 nums，请你将该数组升序排列。
 *
 * 提示：
 * 1 <= nums.length <= 5 * 104
 * -5 * 104 <= nums[i] <= 5 * 104
 *
 */
public class SortArray {
    /**
     * 思路 ：
     * 1.调用Arrays工具类中所提供的sort方法;
     * 2.冒泡排序（超时问题）
     * 3.计数排序；
     * ===》
     * （1）即，使用一个辅助数组，其取值范围包含[最小值 ， 最大值];
     * （2）遍历原数组nums，在辅助数组中统计各个元素出现的频率;
     * （3）最后，从小到大去遍历辅助数组，同时将辅助数组中中所对应的值，填写到nums数组中;
     *
     * 4.快速排序 :
     * ===》
     * 即，选取随机值nums[random]，使得在nums[random]左边的所有元素都 <= nums[random] && nums[random]右边的所有元素都 > nums[random];
     *
     * 5.归并排序 ：
     * ===》
     *
     *
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
//        1.调用Arrays工具类
//        Arrays.sort(nums);
//        return nums;

        // 2.冒泡排序
        // 时间复杂度 ：O(n^2)
        // ===》会导致超时;
//        int len =  nums.length;
//        for(int i = 0 ; i < len ; i++){
//            for(int j = i + 1 ; j < len ; j++){
//                if(nums[i] > nums[j]){
//                    int temp = nums[i];
//                    nums[i] = nums[j];
//                    nums[j] = temp;
//                }
//            }
//        }
//        return nums;

        // 3.计数排序（超时）
//        int[] dp = new int[100001];
//        for(int i = 0 ; i < nums.length ; i++){
//            dp[nums[i] + 50000]++;
//        }
//        int k = 0;
//        for(int i = 0 ; i < 100000 ; i++){
//            while(dp[i] > 0){
//                nums[k++] = i - 50000;
//                dp[i]--;
//            }
//        }
//        return nums;

        // 4.快速排序
        QuickedSorted(nums , 0 , nums.length - 1);
        return nums;

        // 5.归并排序 ：

    }
    // 快排思想的实现 ：
    private void QuickedSorted(int[] nums, int start, int end) {
        // 快速排序结束条件 ：start < end
        if(start < end){
            // 获取 指定random元素进行快速排序之后，其在nums数组中的下标位置;
            int pos = Partition(nums , start , end);
            // nums数组在pos下标左边的所有元素 < nums[pos] && nums数组在pos下标右边的所有元素都是 > nums[pos]的
            QuickedSorted(nums , start , pos - 1);
            QuickedSorted(nums , pos + 1 , end);
        }
    }
    // 选取随机值random，满足该nums[random]的左面 <= nums[random] && nums[random]的右面 > nums[random];
    private int Partition(int[] nums, int start, int end) {
        // 1.选取随机值
        int index = new Random().nextInt(end - start + 1) +start;
        int p1 = start - 1;
        // 2.将所选取的随机值nums[random]与nums[end]进行元素交换
        /**
         * 为什么要将nums[random]与nums[random]进行交换呢 ？
         * ===》
         * （1）只需要顺序遍历nums数组（除了尾元素）;
         * （2）若是出现小于等于尾元素，都放置到左边;
         * （3）最后，将nums[random]放回即可;
         *
         */
        swap(nums , index , end);
        // 3.遍历所有元素，将小于nums[random]的元素都放置到random的左边;
        for(int i = start ; i < end ; i++){
            if(nums[i] <= nums[end]){
                p1++;
                swap(nums , p1 , i);
            }
        }
        // 4.最后，将存储在数组尾部的nums[index]归位即可;
        p1++;
        swap(nums , p1 , end);
        return p1;
    }

    private void swap(int[] nums, int index, int end) {
        int temp = nums[index];
        nums[index] = nums[end];
        nums[end] = temp;
    }
}
